package com.tys.algorithm.advanced.code.class09;

import java.util.ArrayList;

/**
 * 找中点
 * 快慢指针
 */
public class Code01_LinkedListMid {

    /**
     * 单链表结构
     */
    public static class Node {
        public int value;
        public Node next;

        public Node(int v) {
            value = v;
        }
    }

    //中点或上中点： head 头
    //链表奇数个，返回唯一中点，偶数个则返回上中点
    //	0 -> 1 -> 2 -> 3 -> 4 -> 5
    //2是上中点
    //3是下中点
    public static Node midOrUpMidNode(Node head) {
        //<3个节点
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }
        // 链表有3个点或以上
        //从第2个开始：快指针起点比慢指针起点领先1
        Node slow = head.next;
        Node fast = head.next.next;
        //慢指针一次1步，快指针一次2步
        //快指针完了，慢指针在一半位置
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //返回慢指针
        return slow;
    }

    //中点点或下中点：链表奇数个，返回唯一中点，偶数个则返回下中点
    public static Node midOrDownMidNode(Node head) {
        // < 2个
        if (head == null || head.next == null) {
            return head;
        }
        //从第2个开始：快慢指针起点相同
        Node slow = head.next;
        Node fast = head.next;
        //慢指针一次1步，快指针一次2步
        //快指针完了，慢指针在一半位置
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    //链表奇数个，返回中点前一个节点， 偶数个返回上中点前一个
    public static Node midOrUpMidPreNode(Node head) {
        // < 3 个节点
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        //从第1个开始：快指针比慢指针领先2个
        Node slow = head;
        Node fast = head.next.next;
        //慢指针一次1步，快指针一次2步
        //快指针完了，慢指针在一半位置
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    //链表奇数个，返回中点前一个节点， 偶数个返回下中点前一个
    public static Node midOrDownMidPreNode(Node head) {
        if (head == null || head.next == null) {
            return null;
        }
        if (head.next.next == null) {
            return head;
        }
        //从第1个开始：快指针比慢指针领先1
        Node slow = head;
        Node fast = head.next;
        //慢指针一次1步，快指针一次2步
        //快指针完了，慢指针在一半位置
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    //使用容器：链表奇数个返回唯一中点，偶数个返回上中点
    public static Node right1(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        ArrayList<Node> arr = new ArrayList<>();
        while (cur != null) {
            arr.add(cur);
            cur = cur.next;
        }
        return arr.get((arr.size() - 1) / 2);
    }

    //使用容器：链表奇数个返回唯一中点，偶数个返回下中点
    public static Node right2(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        ArrayList<Node> arr = new ArrayList<>();
        while (cur != null) {
            arr.add(cur);
            cur = cur.next;
        }
        return arr.get(arr.size() / 2);
    }

    //使用容器：链表奇数个返回中点前一个，偶数个返回上中点前一个
    public static Node right3(Node head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        Node cur = head;
        ArrayList<Node> arr = new ArrayList<>();
        while (cur != null) {
            arr.add(cur);
            cur = cur.next;
        }
        return arr.get((arr.size() - 3) / 2);
    }

    //使用容器：链表奇数个返回中点前一个，偶数个返回下中点前一个
    public static Node right4(Node head) {
        if (head == null || head.next == null) {
            return null;
        }
        Node cur = head;
        ArrayList<Node> arr = new ArrayList<>();
        while (cur != null) {
            arr.add(cur);
            cur = cur.next;
        }
        return arr.get((arr.size() - 2) / 2);
    }

    public static void main(String[] args) {
        Node test = null;
        test = new Node(0);
        test.next = new Node(1);
        test.next.next = new Node(2);
        test.next.next.next = new Node(3);
        test.next.next.next.next = new Node(4);
        test.next.next.next.next.next = new Node(5);
        test.next.next.next.next.next.next = new Node(6);
        test.next.next.next.next.next.next.next = new Node(7);
        test.next.next.next.next.next.next.next.next = new Node(8);

        Node ans1 = null;
        Node ans2 = null;

        ans1 = midOrUpMidNode(test);
        ans2 = right1(test);
        System.out.println(ans1 != null ? ans1.value : "无");
        System.out.println(ans2 != null ? ans2.value : "无");

        ans1 = midOrDownMidNode(test);
        ans2 = right2(test);
        System.out.println(ans1 != null ? ans1.value : "无");
        System.out.println(ans2 != null ? ans2.value : "无");

        ans1 = midOrUpMidPreNode(test);
        ans2 = right3(test);
        System.out.println(ans1 != null ? ans1.value : "无");
        System.out.println(ans2 != null ? ans2.value : "无");

        ans1 = midOrDownMidPreNode(test);
        ans2 = right4(test);
        System.out.println(ans1 != null ? ans1.value : "无");
        System.out.println(ans2 != null ? ans2.value : "无");

    }

}
